{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Number of Flips to Convert Binary Matrix to Zero Matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #breadth-first-search #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #广度优先搜索 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minFlips"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #转化为全零矩阵的最少反转次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个&nbsp;<code>m x n</code>&nbsp;的二进制矩阵&nbsp;<code>mat</code>。每一步，你可以选择一个单元格并将它反转（反转表示 <code>0</code> 变 <code>1</code> ，<code>1</code> 变 <code>0</code> ）。如果存在和它相邻的单元格，那么这些相邻的单元格也会被反转。相邻的两个单元格共享同一条边。</p>\n",
    "\n",
    "<p>请你返回将矩阵&nbsp;<code>mat</code> 转化为全零矩阵的<em>最少反转次数</em>，如果无法转化为全零矩阵，请返回&nbsp;<code>-1</code>&nbsp;。</p>\n",
    "\n",
    "<p><strong>二进制矩阵</strong>&nbsp;的每一个格子要么是 <code>0</code> 要么是 <code>1</code> 。</p>\n",
    "\n",
    "<p><strong>全零矩阵</strong>&nbsp;是所有格子都为 <code>0</code> 的矩阵。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/12/13/matrix.png\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>mat = [[0,0],[0,1]]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>一个可能的解是反转 (1, 0)，然后 (0, 1) ，最后是 (1, 1) 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>mat = [[0]]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>给出的矩阵是全零矩阵，所以你不需要改变它。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>mat = [[1,0,0],[1,0,0]]\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>该矩阵无法转变成全零矩阵\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m ==&nbsp;mat.length</code></li>\n",
    "\t<li><code>n ==&nbsp;mat[0].length</code></li>\n",
    "\t<li><code>1 &lt;= m&nbsp;&lt;= 3</code></li>\n",
    "\t<li><code>1 &lt;= n&nbsp;&lt;= 3</code></li>\n",
    "\t<li><code>mat[i][j]</code>&nbsp;是 0 或 1 。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-number-of-flips-to-convert-binary-matrix-to-zero-matrix](https://leetcode.cn/problems/minimum-number-of-flips-to-convert-binary-matrix-to-zero-matrix/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-number-of-flips-to-convert-binary-matrix-to-zero-matrix](https://leetcode.cn/problems/minimum-number-of-flips-to-convert-binary-matrix-to-zero-matrix/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,0],[0,1]]', '[[0]]', '[[1,0,0],[1,0,0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        temp = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j]:\n",
    "                    temp |= (1 << i*n+j)\n",
    "        visit = set([temp])\n",
    "        q = deque([(temp, 0)])\n",
    "        while q:\n",
    "            now, dist = q.popleft()\n",
    "            if now == 0:\n",
    "                return dist\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    nex = now\n",
    "                    for a, b in [(i, j), (i-1, j), (i+1, j), (i, j-1), (i, j+1)]:\n",
    "                        if 0 <= a < m and 0 <= b < n:\n",
    "                            if now & (1 << a*n+b):\n",
    "                                nex &= ~(1 << a*n+b)\n",
    "                            else:\n",
    "                                nex |= (1 << a*n+b)\n",
    "                    if nex not in visit:\n",
    "                        q.append((nex, dist+1))\n",
    "                        visit.add(nex)           \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        m,n = len(mat),len(mat[0])\n",
    "        # 矩阵转二进制数\n",
    "        def encode(mat):\n",
    "            x = 0\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    x = x*2 + mat[i][j]\n",
    "            return x\n",
    "        # 二进制数转矩阵\n",
    "        def decode(x):\n",
    "            mat = [[0]*n for _ in range(m)]\n",
    "            for i in range(m-1,-1,-1):\n",
    "                for j in range(n-1,-1,-1):\n",
    "                    mat[i][j] = x&1\n",
    "                    x >>= 1\n",
    "            return mat\n",
    "        def convert(state,i,j):\n",
    "            for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1), (0, 0)]:\n",
    "                i0, j0 = i + di, j + dj\n",
    "                if 0 <= i0 < m and 0 <= j0 < n:\n",
    "                    state[i0][j0] ^= 1\n",
    "        # 广度优先搜索\n",
    "        initial = encode(mat)\n",
    "        step = 0\n",
    "        if initial == 0:return step\n",
    "        seen = {initial}\n",
    "        q = [initial]\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for x in tmp:\n",
    "                state = decode(x)\n",
    "                # 枚举翻转的位置\n",
    "                for i in range(m):\n",
    "                    for j in range(n):\n",
    "                        # 翻转一次\n",
    "                        convert(state,i,j)\n",
    "                        y = encode(state)\n",
    "                        if y == 0:\n",
    "                            return step+1\n",
    "                        if y not in seen:\n",
    "                            q.append(y)\n",
    "                            seen.add(y)\n",
    "                        # 翻转回去\n",
    "                        convert(state,i,j)\n",
    "            step += 1        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        vv = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                vv = (vv << 1) + mat[i][j]\n",
    "        if vv == 0: return 0\n",
    "        ans = [-1] * (1 << m * n)\n",
    "        ans[0] = 0\n",
    "        q = [0]\n",
    "        d = 0\n",
    "        while q:\n",
    "            t = []\n",
    "            for v in q:\n",
    "                for s in range(m * n):\n",
    "                    i, j = divmod(s, n)\n",
    "                    nv = v ^ (1 << s)\n",
    "                    for di, dj in ((-1, 0), (1, 0), (0, -1), (0, 1)):\n",
    "                        ni, nj = i + di, j + dj\n",
    "                        if ni < 0 or ni >= m or nj < 0 or nj >= n: continue\n",
    "                        nv ^= 1 << (ni * n + nj)\n",
    "                    if ans[nv] == -1:\n",
    "                        ans[nv] = d + 1\n",
    "                        if vv == nv: return d + 1\n",
    "                        t.append(nv)\n",
    "            d += 1\n",
    "            q = t\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, mat, m, n, i, j):\n",
    "        for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1), (0, 0)]:\n",
    "            i0, j0 = i + di, j + dj\n",
    "            if 0 <= i0 < m and 0 <= j0 < n:\n",
    "                mat[i0][j0] ^= 1\n",
    "\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        ans = 1e9\n",
    "        for binary in range(0, 1 << n):\n",
    "            mat_copy = [line[:] for line in mat]\n",
    "            flip_cnt = 0\n",
    "            for j in range(n):\n",
    "                if binary & (1 << j):\n",
    "                    flip_cnt += 1\n",
    "                    self.convert(mat_copy, m, n, 0, j)\n",
    "\n",
    "            for i in range(1, m):\n",
    "                for j in range(n):\n",
    "                    if mat_copy[i - 1][j] == 1:\n",
    "                        flip_cnt += 1\n",
    "                        self.convert(mat_copy, m, n, i, j)\n",
    "\n",
    "            if all(mat_copy[m - 1][j] == 0 for j in range(n)):\n",
    "                ans = min(ans, flip_cnt)\n",
    "        return ans if ans != 10**9 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        \n",
    "        m, n = len(mat), len(mat[0])\n",
    "        visit = set()\n",
    "        lst = []\n",
    "        for ma in mat:\n",
    "            lst.extend(ma)\n",
    "        visit.add(tuple(lst))\n",
    "        stack = deque([[lst, 0]])\n",
    "        while stack:\n",
    "            lst, d = stack.popleft()\n",
    "            if all(x==0 for x in lst):\n",
    "                return d\n",
    "            for i in range(m*n):\n",
    "                x, y = i//n, i%n\n",
    "                tmp = lst[:]\n",
    "                tmp[i] = 1-tmp[i]\n",
    "                for a, b in [[x-1, y], [x+1, y], [x, y-1], [x, y+1]]:\n",
    "                    if 0<=a<m and 0<=b<n:\n",
    "                        tmp[a*n+b] = 1-tmp[a*n+b]\n",
    "                if tuple(tmp) not in visit:\n",
    "                    visit.add(tuple(tmp))\n",
    "                    stack.append([tmp, d+1])\n",
    "                \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        \n",
    "        def flip(x, y):\n",
    "            directions = [(0, 0), (0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "            for dx, dy in directions:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < m and 0 <= ny < n:\n",
    "                    mat[nx][ny] = 1 - mat[nx][ny]\n",
    "        \n",
    "        def check_zero_matrix(mat):\n",
    "            for row in mat:\n",
    "                for num in row:\n",
    "                    if num != 0:\n",
    "                        return False\n",
    "            return True\n",
    "        \n",
    "        def dfs(x, y):\n",
    "            if x == m:\n",
    "                if check_zero_matrix(mat):\n",
    "                    self.min_flips = min(self.min_flips, self.flip_count)\n",
    "                return\n",
    "            if y == n:\n",
    "                dfs(x + 1, 0)\n",
    "                return\n",
    "            \n",
    "            # 不反转当前格子\n",
    "            dfs(x, y + 1)\n",
    "            \n",
    "            # 反转当前格子\n",
    "            flip(x, y)\n",
    "            self.flip_count += 1\n",
    "            dfs(x, y + 1)\n",
    "            flip(x, y)  # 恢复原始状态\n",
    "            self.flip_count -= 1\n",
    "        \n",
    "        self.min_flips = float('inf')\n",
    "        self.flip_count = 0\n",
    "        dfs(0, 0)\n",
    "        \n",
    "        return self.min_flips if self.min_flips != float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        def stack(i, j):#以i，j为中心反转\n",
    "            for x, y in [[i, j], [i + 1, j], [i - 1, j], [i, j + 1], [i, j - 1]]:\n",
    "                if 0 <= x < m and 0 <= y < n:\n",
    "                    mat[x][y] = 0 if mat[x][y] == 1 else 1\n",
    "            \n",
    "        def dfs(state):#状态位\n",
    "            if state == m * n:#如果所有点遍历完了\n",
    "                return 0 if sum(sum(i) for i in mat) == 0 else float(\"inf\")#根据是否有1来决定返回0或者inf\n",
    "            x, y = state // n, state % n#状态位转横纵坐标\n",
    "            res = dfs(state + 1)#不反转的结果\n",
    "            stack(x, y)#反转\n",
    "            res = min(res, 1 + dfs(state + 1))#找到和反转后的最小值\n",
    "            stack(x, y)#再次反转回溯\n",
    "            return res\n",
    "\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        res = dfs(0)\n",
    "        return res if res < float(\"inf\") else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        mask = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j]:\n",
    "                    mask |= 1 << (i * n + j)\n",
    "\n",
    "        q = deque([(mask, 0)])\n",
    "        vis = {mask, }\n",
    "        while q:\n",
    "            cur, step = q.popleft()\n",
    "            if cur == 0:\n",
    "                return step\n",
    "            for i in range(m * n):\n",
    "                r, c = divmod(i, n)  # 获取i的行，列\n",
    "                nxt = cur\n",
    "                for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):\n",
    "                    if 0 <= nr < m and 0 <= nc < n:\n",
    "                        nxt ^= 1 << (nr * n + nc)  # 翻转i的四边\n",
    "                nxt ^= 1 << (r * n + c)  # 翻转i\n",
    "                if nxt not in vis:\n",
    "                    vis.add(nxt)\n",
    "                    q.append((nxt, step + 1))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        m,n = len(mat),len(mat[0])\n",
    "        # 矩阵转二进制数\n",
    "        def encode(mat):\n",
    "            x = 0\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    x = x*2 + mat[i][j]\n",
    "            return x\n",
    "        # 二进制数转矩阵\n",
    "        def decode(x):\n",
    "            mat = [[0]*n for _ in range(m)]\n",
    "            for i in range(m-1,-1,-1):\n",
    "                for j in range(n-1,-1,-1):\n",
    "                    mat[i][j] = x&1\n",
    "                    x >>= 1\n",
    "            return mat\n",
    "        def convert(state,i,j):\n",
    "            for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1), (0, 0)]:\n",
    "                i0, j0 = i + di, j + dj\n",
    "                if 0 <= i0 < m and 0 <= j0 < n:\n",
    "                    state[i0][j0] ^= 1\n",
    "            return state\n",
    "        # 广度优先搜索\n",
    "        initial = encode(mat)\n",
    "        step = 0\n",
    "        if initial == 0:return step\n",
    "        seen = {initial}\n",
    "        q = [initial]\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for x in tmp:\n",
    "                state = decode(x)\n",
    "                for i in range(m):\n",
    "                    for j in range(n):\n",
    "                        state = convert(state,i,j)\n",
    "                        y = encode(state)\n",
    "                        if y == 0:\n",
    "                            return step+1\n",
    "                        if y not in seen:\n",
    "                            q.append(y)\n",
    "                            seen.add(y)\n",
    "                        state = convert(state,i,j)\n",
    "            step += 1        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        s=set()\n",
    "        q=[(mat,0)]\n",
    "        while (len(q)!=0):\n",
    "            q0=q.pop(0)\n",
    "            # print(q0,q)\n",
    "            s.add(self.flat(q0[0]))\n",
    "            if self.test(q0[0]):\n",
    "                return q0[1]\n",
    "            # print(q0[0])\n",
    "            m,n=len(q0[0]),len(q0[0][0])\n",
    "            # print(self.flat(q0[0]))\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    # print(i,j)\n",
    "                    tempmat=copy.deepcopy(q0[0])\n",
    "                    # print(tempmat)\n",
    "                    tempmat[i][j]=1-tempmat[i][j]\n",
    "                    if i-1>=0:\n",
    "                        tempmat[i-1][j]=1-tempmat[i-1][j]\n",
    "                    if i+1<m:\n",
    "                        tempmat[i+1][j]=1-tempmat[i+1][j]\n",
    "                    if j-1>=0:\n",
    "                        tempmat[i][j-1]=1-tempmat[i][j-1]\n",
    "                    if j+1<n:\n",
    "                        tempmat[i][j+1]=1-tempmat[i][j+1]\n",
    "                    # print(tempmat)\n",
    "                    if self.flat(tempmat) not in s:\n",
    "                        q.append((tempmat, q0[1]+1))\n",
    "                        s.add(self.flat(tempmat))\n",
    "        return -1\n",
    "\n",
    "    def test(self, mat):\n",
    "        res=True\n",
    "        for i in range(len(mat)):\n",
    "            for j in range(len(mat[0])):\n",
    "                if mat[i][j]!=0:\n",
    "                    res=False\n",
    "        return res\n",
    "\n",
    "    def flat(self, mat):\n",
    "        x=0\n",
    "        res=0\n",
    "        for i in range(len(mat)):\n",
    "            for j in range(len(mat[0])):\n",
    "                res+= pow(10,x)*mat[i][j]\n",
    "                x+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def encode(self, mat, m, n):\n",
    "        x = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                x = x * 2 + mat[i][j]\n",
    "        return x\n",
    "    \n",
    "    def decode(self, x, m, n):\n",
    "        mat = [[0] * n for _ in range(m)]\n",
    "        for i in range(m-1, -1, -1):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                mat[i][j] = x & 1\n",
    "                x >>= 1\n",
    "        return mat\n",
    "    \n",
    "    def convert(self, mat, m, n, i, j):\n",
    "        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1), (0, 0)]\n",
    "        for di, dj in dirs:\n",
    "            ni, nj = i + di, j + dj\n",
    "            if 0 <= ni <= m-1 and 0 <= nj <=n-1:\n",
    "                mat[ni][nj] ^= 1\n",
    "\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        x_start = self.encode(mat, m, n)\n",
    "        step = 0\n",
    "        if x_start == 0:\n",
    "            return step\n",
    "\n",
    "        q = deque()\n",
    "        q.append(x_start)\n",
    "        \n",
    "        vis = {x_start}\n",
    "        \n",
    "        while q:\n",
    "            step += 1\n",
    "            for _ in range(len(q)):\n",
    "                # 列表中存的是10进制\n",
    "                cur_x = q.popleft()\n",
    "                # 从当前状态中进行枚举\n",
    "                status = self.decode(cur_x, m, n)\n",
    "                for i in range(m):\n",
    "                    for j in range(n):\n",
    "                        self.convert(status, m, n, i, j)\n",
    "                        new_x = self.encode(status, m, n)\n",
    "                        if new_x == 0:\n",
    "                            return step\n",
    "                        if not new_x in vis:\n",
    "                            q.append(new_x)\n",
    "                            vis.add(new_x)\n",
    "                        # 需要把状态再恢复回去\n",
    "                        self.convert(status, m, n, i, j)\n",
    "        return -1\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        self.m, self.n = len(mat), len(mat[0])\n",
    "\n",
    "        def dfs(num: int, i: int, j: int) -> int:\n",
    "            if i >= self.m or j >= self.n:\n",
    "                return inf if num else 0\n",
    "            x = i + 1 if j == self.n - 1 else i\n",
    "            y = 0 if j == self.n - 1 else j + 1\n",
    "            return min(dfs(self.convert(num, i, j), x, y) + 1, dfs(num, x, y))\n",
    "\n",
    "        ans = dfs(self.enconde(mat), 0, 0)\n",
    "        return -1 if ans == inf else ans\n",
    "            \n",
    "\n",
    "    def enconde(self, mat: List[List[int]]) -> int:\n",
    "        num = 0\n",
    "        for i, row in enumerate(mat):\n",
    "            for j, x in enumerate(row):\n",
    "                if x:\n",
    "                    num |= (1 << (i * self.n + j))\n",
    "        return num\n",
    "\n",
    "    def convert(self, num: int, x: int, y: int) -> List[List[int]]:\n",
    "        d = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        for dx, dy in d:\n",
    "            if 0 <= x + dx < self.m and 0 <= y + dy < self.n:\n",
    "                num ^= (1 << ((x + dx) * self.n + y + dy))\n",
    "        num ^= (1 << (x * self.n + y))\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ans = 10**9\n",
    "\n",
    "    def convert(self, mat, m, n, i, j):\n",
    "        for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1), (0, 0)]:\n",
    "            i0, j0 = i + di, j + dj\n",
    "            if 0 <= i0 < m and 0 <= j0 < n:\n",
    "                mat[i0][j0] ^= 1\n",
    "\n",
    "    def dfs(self, mat, m, n, pos, flip_cnt):\n",
    "        if pos == m * n:\n",
    "            if all(mat[i][j] == 0 for i in range(m) for j in range(n)):\n",
    "                self.ans = min(self.ans, flip_cnt)\n",
    "            return\n",
    "\n",
    "        x, y = pos // n, pos % n\n",
    "        # not flip\n",
    "        self.dfs(mat, m, n, pos + 1, flip_cnt)\n",
    "        # flip\n",
    "        self.convert(mat, m, n, x, y)\n",
    "        self.dfs(mat, m, n, pos + 1, flip_cnt + 1)\n",
    "        self.convert(mat, m, n, x, y)\n",
    "\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        self.dfs(mat, m, n, 0, 0)\n",
    "        return self.ans if self.ans != 10**9 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, mat, m, n, i, j):\n",
    "        for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1), (0, 0)]:\n",
    "            i0, j0 = i + di, j + dj\n",
    "            if 0 <= i0 < m and 0 <= j0 < n:\n",
    "                mat[i0][j0] ^= 1\n",
    "\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        ans = 1e9\n",
    "        for binary in range(0, 1 << n):\n",
    "            mat_copy = [line[:] for line in mat]\n",
    "            flip_cnt = 0\n",
    "            for j in range(n):\n",
    "                if binary & (1 << j):\n",
    "                    flip_cnt += 1\n",
    "                    self.convert(mat_copy, m, n, 0, j)\n",
    "\n",
    "            for i in range(1, m):\n",
    "                for j in range(n):\n",
    "                    if mat_copy[i - 1][j] == 1:\n",
    "                        flip_cnt += 1\n",
    "                        self.convert(mat_copy, m, n, i, j)\n",
    "\n",
    "            if all(mat_copy[m - 1][j] == 0 for j in range(n)):\n",
    "                ans = min(ans, flip_cnt)\n",
    "        return ans if ans != 10**9 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        m,n = len(mat),len(mat[0])\n",
    "        def encode(mat):\n",
    "            res = 0\n",
    "            # 矩阵变二进制数\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    res = res*2+mat[i][j]\n",
    "            return res\n",
    "        def otcode(x):\n",
    "            # 二进制数变成矩阵\n",
    "            res = [[0]*n for _ in range(m)]\n",
    "            for i in range(m-1,-1,-1):\n",
    "                for j in range(n-1,-1,-1):\n",
    "                    res[i][j] = x & 1\n",
    "                    x >>= 1\n",
    "            return res\n",
    "        # def exchange(mat,i,j):\n",
    "        #     for x,y in (i,j),(i-1,j),(i+1,j),(i,j-1),(i,j+1):\n",
    "        #         if 0 <= x < m and 0 <= y < n:\n",
    "        #             mat[i][j] ^= 1\n",
    "        def exchange(state,i,j):\n",
    "            for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1), (0, 0)]:\n",
    "                i0, j0 = i + di, j + dj\n",
    "                if 0 <= i0 < m and 0 <= j0 < n:\n",
    "                    state[i0][j0] ^= 1\n",
    "        # BFS\n",
    "        initial = encode(mat)\n",
    "        step = 0\n",
    "        if initial == 0:return step\n",
    "        q = [initial]\n",
    "        seen = {initial}\n",
    "        \n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for x in tmp:\n",
    "                # 二进制数转为矩阵\n",
    "                state = otcode(x)\n",
    "                # 枚举翻转的位置\n",
    "                for i in range(m):\n",
    "                    for j in range(n):\n",
    "                        exchange(state,i,j)\n",
    "                        # 翻转完毕转为二进制数\n",
    "                        y = encode(state)\n",
    "                        if y == 0:return step+1\n",
    "                        if y not in seen:\n",
    "                            q.append(y)\n",
    "                            seen.add(y)\n",
    "                        # 翻转回去\n",
    "                        exchange(state,i,j)\n",
    "                        \n",
    "            step += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        self.m, self.n = len(mat), len(mat[0])\n",
    "\n",
    "        def dfs(num: int, i: int, j: int) -> int:\n",
    "            if i >= self.m or j >= self.n:\n",
    "                return inf if num else 0\n",
    "            x = i + 1 if j == self.n - 1 else i\n",
    "            y = 0 if j == self.n - 1 else j + 1\n",
    "            if i != 0 and num & (1 << ((i - 1) * self.n + j)):\n",
    "                return dfs(self.convert(num, i, j), x, y) + 1\n",
    "            if i != 0 and num & (1 << ((i - 1) * self.n + j)) == 0:\n",
    "                return dfs(num, x, y)\n",
    "            return min(dfs(self.convert(num, i, j), x, y) + 1, dfs(num, x, y))\n",
    "\n",
    "        ans = dfs(self.enconde(mat), 0, 0)\n",
    "        return -1 if ans == inf else ans\n",
    "            \n",
    "\n",
    "    def enconde(self, mat: List[List[int]]) -> int:\n",
    "        num = 0\n",
    "        for i, row in enumerate(mat):\n",
    "            for j, x in enumerate(row):\n",
    "                if x:\n",
    "                    num |= (1 << (i * self.n + j))\n",
    "        return num\n",
    "\n",
    "    def convert(self, num: int, x: int, y: int) -> List[List[int]]:\n",
    "        d = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        for dx, dy in d:\n",
    "            if 0 <= x + dx < self.m and 0 <= y + dy < self.n:\n",
    "                num ^= (1 << ((x + dx) * self.n + y + dy))\n",
    "        num ^= (1 << (x * self.n + y))\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        def stack(i, j):#以i，j为中心反转\n",
    "            for x, y in [[i, j], [i + 1, j], [i - 1, j], [i, j + 1], [i, j - 1]]:\n",
    "                if 0 <= x < m and 0 <= y < n:\n",
    "                    mat[x][y] = 0 if mat[x][y] == 1 else 1\n",
    "            \n",
    "        def dfs(state):#状态位\n",
    "            if state == m * n:#如果所有点遍历完了\n",
    "                return 0 if sum(sum(i) for i in mat) == 0 else float(\"inf\")#根据是否有1来决定返回0或者inf\n",
    "            x, y = state // n, state % n#状态位转横纵坐标\n",
    "            res = dfs(state + 1)#不反转的结果\n",
    "            stack(x, y)#反转\n",
    "            res = min(res, 1 + dfs(state + 1))#找到和反转后的最小值\n",
    "            stack(x, y)#再次反转回溯\n",
    "            return res\n",
    "\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        res = dfs(0)\n",
    "        return res if res < float(\"inf\") else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        def jd(s):\n",
    "            s = s.rjust(m*n, \"0\")\n",
    "            for x in range(m):\n",
    "                for y in range(n):\n",
    "                    v = mat[x][y]\n",
    "                    for dx, dy in POS:\n",
    "                        nx, ny = x + dx, y + dy\n",
    "                        if 0 <= nx < m and 0 <= ny < n and s[nx*n+ny] == \"1\": v = 1 - v\n",
    "                    if v: return False\n",
    "            return True\n",
    "        m, n, POS, res = len(mat), len(mat[0]), ((0,0), (0, 1), (1, 0), (0, -1), (-1, 0)), 10\n",
    "        for k in range(1<<m*n):\n",
    "            bk = bin(k)[2:]\n",
    "            if res > bk.count(\"1\"):\n",
    "                if jd(bk): res = bk.count(\"1\")\n",
    "        return res if res < 10 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        self.m, self.n = len(mat), len(mat[0])\n",
    "\n",
    "        dq = deque([self.enconde(mat)])\n",
    "        v = set([self.enconde(mat)])\n",
    "        steps = 0\n",
    "        while dq:\n",
    "            size = len(dq)\n",
    "            while size:\n",
    "                o = dq.popleft()\n",
    "                if o == 0:\n",
    "                    return steps\n",
    "                for i in range(self.m):\n",
    "                    for j in range(self.n):\n",
    "                        p = self.convert(o, i, j)\n",
    "                        if p in v:\n",
    "                            continue\n",
    "                        dq.append(p)\n",
    "                        v.add(p)\n",
    "                size -= 1\n",
    "            steps += 1\n",
    "        return -1\n",
    "\n",
    "    def enconde(self, mat: List[List[int]]) -> int:\n",
    "        num = 0\n",
    "        for i, row in enumerate(mat):\n",
    "            for j, x in enumerate(row):\n",
    "                if x:\n",
    "                    num |= (1 << (i * self.n + j))\n",
    "        return num\n",
    "\n",
    "    def decode(self, num: int) -> List[List[int]]:\n",
    "        mat = [[0] * self.n for _ in range(self.m)]\n",
    "        for x in range(num.bit_length()):\n",
    "            if num & (1 << x):\n",
    "                i, j = divmod(x, self.n)\n",
    "                mat[i][j] = 1\n",
    "        return mat\n",
    "\n",
    "    def convert(self, num: int, x: int, y: int) -> List[List[int]]:\n",
    "        d = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        for dx, dy in d:\n",
    "            if 0 <= x + dx < self.m and 0 <= y + dy < self.n:\n",
    "                num ^= (1 << ((x + dx) * self.n + y + dy))\n",
    "        num ^= (1 << (x * self.n + y))\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        target = \"0\" * (m*n)\n",
    "\n",
    "        #print(target)\n",
    "\n",
    "        def encode(mat):\n",
    "            res = ''\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    res += str(mat[i][j])\n",
    "            return res\n",
    "        \n",
    "        def decode(s):\n",
    "            res = [[0] * n for _ in range(m)]\n",
    "            for i, si in enumerate(s):\n",
    "                idx, idy = divmod(i, n)\n",
    "                res[idx][idy] = int(si)\n",
    "            return res\n",
    "        \n",
    "        def change(x,y,mat):\n",
    "            mat[x][y] ^= 1\n",
    "            for dx, dy in (x+1, y), (x, y+1), (x-1, y), (x,y-1):\n",
    "                if 0<= dx < m and 0<= dy < n:\n",
    "                    mat[dx][dy] ^= 1\n",
    "            return mat\n",
    "\n",
    "        start = encode(mat)\n",
    "        q = [(0, start)]\n",
    "        visit = set()\n",
    "        visit.add(start)\n",
    "        while q:\n",
    "            #print(q)\n",
    "            ti, qi = heappop(q)\n",
    "            if qi == target:\n",
    "                return ti\n",
    "            \n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    matqi = decode(qi)\n",
    "                    matij = change(i,j,matqi)\n",
    "                    #print(matqi)\n",
    "                    smatij = encode(matij)\n",
    "                    if smatij not in visit:\n",
    "                        heappush(q, (ti+1, smatij))\n",
    "                        visit.add(smatij)\n",
    "                   \n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        target = \"0\" * (m * n)\n",
    "        cur = ''\n",
    "        mapper = {\"0\": '1', \"1\": '0'}\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                cur = cur + str(mat[i][j])\n",
    "        \n",
    "        def flip(s, j):\n",
    "            s[j] = mapper[s[j]]\n",
    "            if j % n >= 1:\n",
    "                s[j-1] = mapper[s[j-1]]\n",
    "            if j % n < n-1:\n",
    "                s[j+1] = mapper[s[j+1]]\n",
    "            if j >= n:\n",
    "                s[j-n] = mapper[s[j-n]]\n",
    "            if j < (m-1) * n:\n",
    "                s[j+n] = mapper[s[j+n]]\n",
    "            return s\n",
    "\n",
    "\n",
    "        queue = [cur]\n",
    "        visited = set()\n",
    "        cnt = 0 \n",
    "        while len(queue):\n",
    "            for i in range(len(queue)):\n",
    "                cur = queue.pop(0)\n",
    "                if cur == target:\n",
    "                    return cnt\n",
    "                if cur in visited:\n",
    "                    continue\n",
    "                \n",
    "                visited.add(cur)\n",
    "                for j in range(len(cur)):\n",
    "                    s = list(cur)\n",
    "                    s = flip(s, j)\n",
    "                    queue.append(''.join(s))\n",
    "            cnt += 1\n",
    "        \n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        que = deque()\n",
    "        k = m * n\n",
    "        visited = set()\n",
    "        que.append((0, 0))\n",
    "        target = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                target += mat[i][j] * (1 << (i * n + j))\n",
    "        if target == 0:\n",
    "            return 0\n",
    "        while que:\n",
    "            status, step = que.popleft()\n",
    "            for i in range(k):\n",
    "                x, y = i // n, i % n\n",
    "                tmp = status\n",
    "                for dx, dy in ((0, 0), (0, 1), (0, -1), (1, 0), (-1, 0)):\n",
    "                    nx, ny = x + dx, y + dy\n",
    "                    if 0 <= nx < m and 0 <= ny < n:\n",
    "                        tmp ^= (1 << (nx * n + ny))\n",
    "                if tmp == target:\n",
    "                    return step + 1\n",
    "                if tmp not in visited:\n",
    "                    visited.add(tmp)\n",
    "                    que.append((tmp, step + 1))\n",
    "        return -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        res, m, n = inf, len(mat), len(mat[0])\n",
    "        mat, board = [reduce(lambda r, t: r + r + t, row) for row in mat], (1 << n) - 1\n",
    "        def convert(mask, i, tm):\n",
    "            if i + 1 < m: tm[i + 1] ^= mask\n",
    "            tm[i] ^= mask ^ (mask << 1) ^ (mask >> 1) \n",
    "            return tm[i] & board\n",
    "        for mask in range(1 << n):\n",
    "            tr, tm = 0, mat.copy()\n",
    "            for i in range(m):\n",
    "                tr += mask.bit_count()\n",
    "                mask = convert(mask, i, tm)\n",
    "            if mask == 0:\n",
    "                res = min(res, tr)\n",
    "                if res in (0, 1): return res\n",
    "        return res if res < inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def encode(self, mat, m, n):\n",
    "        x = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                x = x * 2 + mat[i][j]\n",
    "        return x\n",
    "    \n",
    "    def decode(self, x, m, n):\n",
    "        mat = [[0] * n for _ in range(m)]\n",
    "        for i in range(m-1, -1, -1):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                mat[i][j] = x & 1\n",
    "                x >>= 1\n",
    "        return mat\n",
    "    \n",
    "    def convert(self, mat, m, n, i, j):\n",
    "        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1), (0, 0)]\n",
    "        for di, dj in dirs:\n",
    "            ni, nj = i + di, j + dj\n",
    "            if 0 <= ni <= m-1 and 0 <= nj <=n-1:\n",
    "                mat[ni][nj] ^= 1\n",
    "\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        x_start = self.encode(mat, m, n)\n",
    "        q = deque()\n",
    "        q.append(x_start)\n",
    "        step = 0\n",
    "        vis = set()\n",
    "        vis.add(x_start)\n",
    "\n",
    "        if x_start == 0:\n",
    "            return step\n",
    "\n",
    "        while q:\n",
    "            step += 1\n",
    "            for _ in range(len(q)):\n",
    "                # 列表中存的是10进制\n",
    "                cur_x = q.popleft()\n",
    "                # 从当前状态中进行枚举\n",
    "                status = self.decode(cur_x, m, n)\n",
    "                for i in range(m):\n",
    "                    for j in range(n):\n",
    "                        self.convert(status, m, n, i, j)\n",
    "                        new_x = self.encode(status, m, n)\n",
    "                        if new_x == 0:\n",
    "                            return step\n",
    "                        if not new_x in vis:\n",
    "                            q.append(new_x)\n",
    "                            vis.add(new_x)\n",
    "                        # 需要把状态再恢复回去\n",
    "                        self.convert(status, m, n, i, j)\n",
    "        return -1\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        \n",
    "        # Convert the matrix into an integer\n",
    "        start = sum(cell << (i * n + j) for i, row in enumerate(mat) for j, cell in enumerate(row))\n",
    "        target = 0\n",
    "        \n",
    "        # Return the neighbors of a given cell\n",
    "        def neighbors(x, y):\n",
    "            for nx, ny in ((x-1, y), (x+1, y), (x, y-1), (x, y+1)):\n",
    "                if 0 <= nx < m and 0 <= ny < n:\n",
    "                    yield nx, ny\n",
    "        \n",
    "        # BFS search\n",
    "        queue = deque([(start, 0)])\n",
    "        seen = {start}\n",
    "        \n",
    "        while queue:\n",
    "            node, steps = queue.popleft()\n",
    "            if node == target: return steps\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    newState = node\n",
    "                    for x, y in neighbors(i, j):\n",
    "                        newState ^= 1 << (x * n + y)\n",
    "                    newState ^= 1 << (i * n + j)  # flip the cell itself\n",
    "                    if newState not in seen:\n",
    "                        seen.add(newState)\n",
    "                        queue.append((newState, steps + 1))\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gen_flips(self, mat):\n",
    "        mat = self.to_list(mat)\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        dirs = [(0, -1), (0, 1), (-1, 0), (1, 0)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                _mat = copy.deepcopy(mat)\n",
    "                _mat[i][j] = 1 - _mat[i][j]\n",
    "                for dx, dy in dirs:\n",
    "                    ii = i + dx\n",
    "                    jj = j + dy\n",
    "                    if 0 <= ii < m and 0 <= jj < n:\n",
    "                        _mat[ii][jj] = 1 - _mat[ii][jj]\n",
    "                yield self.to_tuple(_mat)\n",
    "\n",
    "    def to_tuple(self, mat):\n",
    "        m = len(mat)\n",
    "        for i in range(m):\n",
    "            mat[i] = tuple(mat[i])\n",
    "        return tuple(mat)\n",
    "\n",
    "    def to_list(self, mat):\n",
    "        m = len(mat)\n",
    "        mat = list(mat)\n",
    "        for i in range(m):\n",
    "            mat[i] = list(mat[i])\n",
    "        return mat\n",
    "\n",
    "    def check(self, mat):\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        return all(mat[i][j] == 0 for i in range(m) for j in range(n))\n",
    "\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        q = [self.to_tuple(mat)]\n",
    "        vis = set([q[0]])\n",
    "        step = 0\n",
    "\n",
    "        while q:\n",
    "            tmp = []\n",
    "            for m in q:\n",
    "                print(m)\n",
    "                if self.check(m):\n",
    "                    return step\n",
    "                for next_m in self.gen_flips(m):\n",
    "                    if next_m not in vis:\n",
    "                        vis.add(next_m)\n",
    "                        tmp.append(next_m)\n",
    "            q = tmp\n",
    "            step += 1\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        m,n = len(mat),len(mat[0])\n",
    "        def encode(mat):\n",
    "            res = 0\n",
    "            # 矩阵变二进制数\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    res = res*2+mat[i][j]\n",
    "            return res\n",
    "        def otcode(x):\n",
    "            # 二进制数变成矩阵\n",
    "            res = [[0]*n for _ in range(m)]\n",
    "            for i in range(m-1,-1,-1):\n",
    "                for j in range(n-1,-1,-1):\n",
    "                    res[i][j] = x & 1\n",
    "                    x >>= 1\n",
    "            return res\n",
    "        def exchange(mat,i,j):\n",
    "            for x,y in (i,j),(i-1,j),(i+1,j),(i,j-1),(i,j+1):\n",
    "                if 0 <= x < m and 0 <= y < n:\n",
    "                    mat[x][y] ^= 1\n",
    "        # BFS\n",
    "        initial = encode(mat)\n",
    "        step = 0\n",
    "        if initial == 0:return step\n",
    "        q = [initial]\n",
    "        seen = {initial}\n",
    "        \n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for x in tmp:\n",
    "                # 二进制数转为矩阵\n",
    "                state = otcode(x)\n",
    "                # 枚举翻转的位置\n",
    "                for i in range(m):\n",
    "                    for j in range(n):\n",
    "                        exchange(state,i,j)\n",
    "                        # 翻转完毕转为二进制数\n",
    "                        y = encode(state)\n",
    "                        if y == 0:return step+1\n",
    "                        if y not in seen:\n",
    "                            q.append(y)\n",
    "                            seen.add(y)\n",
    "                        # 翻转回去\n",
    "                        exchange(state,i,j)\n",
    "                        \n",
    "            step += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "\n",
    "        # 放到flip函数外部可以减少计算\n",
    "        mapper = {'0': '1', '1': '0'}\n",
    "\n",
    "        def flip(state: list[str], i: int) -> None:\n",
    "            \n",
    "            state[i] = mapper[state[i]]\n",
    "            \n",
    "            if i % n != 0:\n",
    "                state[i - 1] = mapper[state[i - 1]]\n",
    "            if i % n < n - 1:\n",
    "                state[i + 1] = mapper[state[i + 1]]\n",
    "            if i >= n:\n",
    "                state[i - n] = mapper[state[i - n]]\n",
    "            if i < (m - 1) * n:\n",
    "                state[i + n] = mapper[state[i + n]]\n",
    "        \n",
    "        m, n = len(mat), len(mat[0])\n",
    "        target = '0' * (m * n)\n",
    "        cur = ''.join(str(cell) for row in mat for cell in row)\n",
    "        queue = [cur]\n",
    "        visited = set()\n",
    "        steps = 0\n",
    "\n",
    "        while len(queue) > 0:\n",
    "            for _ in range(len(queue)):\n",
    "                cur = queue.pop(0)\n",
    "                if cur == target:\n",
    "                    return steps\n",
    "                if cur in visited:\n",
    "                    continue\n",
    "                \n",
    "                visited.add(cur)\n",
    "                for i in range(len(cur)):\n",
    "                    s = list(cur)\n",
    "                    flip(s, i)\n",
    "                    queue.append(''.join(s))\n",
    "            steps += 1\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        length = m*n\n",
    "        target = [0]*length\n",
    "        cur = []\n",
    "        for ma in mat:\n",
    "            cur.extend(ma)\n",
    "        if cur == target:\n",
    "            return 0\n",
    "\n",
    "        stack = [cur]\n",
    "        visit = dict()\n",
    "        visit[tuple(cur)] = 1\n",
    "        cnt = 1\n",
    "        while stack:\n",
    "            nex = []\n",
    "            for pre in stack:\n",
    "                for i in range(length):\n",
    "                    cur = pre[:]\n",
    "                    r, c = i//n, i%n\n",
    "                    cur[i] = 1-cur[i]\n",
    "                    if r+1<m:\n",
    "                        cur[r*n+n+c] = 1 - cur[r*n+n+c]\n",
    "                    if r-1>=0:\n",
    "                        cur[r*n-n+c] = 1 - cur[r*n-n+c]\n",
    "                    if c+1<n:\n",
    "                        cur[r*n+c+1] = 1 - cur[r*n+c+1]\n",
    "                    if c-1>=0:\n",
    "                        cur[r*n+c-1] = 1 - cur[r*n+c-1] \n",
    "                    if tuple(cur) not in visit:\n",
    "                        nex.append(cur)\n",
    "                        visit[tuple(cur)] = 1\n",
    "                        if cur == target:\n",
    "                            return cnt\n",
    "            cnt += 1\n",
    "            stack = nex\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "class Solution:\n",
    "    def encode(self, mat, m, n):\n",
    "        x = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                x = x * 2 + mat[i][j]\n",
    "        return x\n",
    "\n",
    "    def decode(self, x, m, n):\n",
    "        mat = [[0] * n for _ in range(m)]\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                mat[i][j] = x & 1\n",
    "                x >>= 1\n",
    "        return mat\n",
    "\n",
    "    def convert(self, mat, m, n, i, j):\n",
    "        for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1), (0, 0)]:\n",
    "            i0, j0 = i + di, j + dj\n",
    "            if 0 <= i0 < m and 0 <= j0 < n:\n",
    "                mat[i0][j0] ^= 1\n",
    "\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        x_start, step = self.encode(mat, m, n), 0\n",
    "        if x_start == 0:\n",
    "            return step\n",
    "\n",
    "        visited = {x_start}\n",
    "        q = queue.Queue()\n",
    "        q.put_nowait(x_start)\n",
    "\n",
    "        while not q.empty():\n",
    "            step += 1\n",
    "            k = q.qsize()\n",
    "            for _ in range(k):\n",
    "                status = self.decode(q.get_nowait(), m, n)\n",
    "                for i in range(m):\n",
    "                    for j in range(n):\n",
    "                        self.convert(status, m, n, i, j)\n",
    "                        x_cur = self.encode(status, m, n)\n",
    "                        if x_cur == 0:\n",
    "                            return step\n",
    "                        if x_cur not in visited:\n",
    "                            visited.add(x_cur)\n",
    "                            q.put_nowait(x_cur)\n",
    "                        self.convert(status, m, n, i, j)\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "from typing import List\n",
    "from copy import deepcopy\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "\n",
    "        all_states = set()\n",
    "\n",
    "        def encode(mat):\n",
    "            s = \"\"\n",
    "            for m in mat:\n",
    "                for n in m:\n",
    "                    s += '0' if n == 0 else '1'\n",
    "            return s\n",
    "\n",
    "        def decode(s):\n",
    "            mat = []\n",
    "            for i in range(m):\n",
    "                lst = []\n",
    "                for j in range(n):\n",
    "                    lst.append(0 if s[n * i + j] == '0' else 1)\n",
    "                mat.append(lst)\n",
    "            return mat\n",
    "        \n",
    "        def all_next(mat):\n",
    "            states = []\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    states.append(flip(mat, i, j))\n",
    "            return states\n",
    "\n",
    "        def flip(mat, i, j):\n",
    "            mat = deepcopy(mat)\n",
    "            mat[i][j] = 1 - mat[i][j]\n",
    "            for x, y in get_neighbors(i, j):\n",
    "                mat[x][y] = 1 - mat[x][y]\n",
    "            return mat\n",
    "\n",
    "        def get_neighbors(i, j):\n",
    "            neighbors = []\n",
    "            for i1, j1 in ((0, -1), (0, 1), (-1, 0), (1, 0)):\n",
    "                x, y = i + i1, j + j1\n",
    "                if x >= 0 and x < m and y >= 0 and y < n:\n",
    "                    neighbors.append((x, y))\n",
    "            return neighbors\n",
    "\n",
    "        FINAL_STATE = \"0\" * (m * n)\n",
    "\n",
    "        if encode(mat) == FINAL_STATE:\n",
    "            return 0\n",
    "\n",
    "        def bfs(state: List[List[int]]):\n",
    "            q = queue.Queue()\n",
    "            steps = 0\n",
    "            q.put_nowait(encode(state))\n",
    "            while not q.empty():\n",
    "                steps += 1\n",
    "                final = False\n",
    "                q1 = queue.Queue()\n",
    "                while not q.empty():\n",
    "                    item = q.get_nowait()\n",
    "                    for nxt in all_next(decode(item)):\n",
    "                        nxt1 = encode(nxt)\n",
    "                        if nxt1 == FINAL_STATE:\n",
    "                            return steps\n",
    "                        if nxt1 not in all_states:\n",
    "                            q1.put_nowait(nxt1)\n",
    "                            all_states.add(nxt1)\n",
    "                if final:\n",
    "                    break\n",
    "                q = q1\n",
    "            return -1\n",
    "        \n",
    "        return bfs(mat)\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    s = Solution()\n",
    "    ans = s.minFlips([[0]])\n",
    "    print(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        searched = {}#minimum depth\n",
    "        code = self.serialize(mat)\n",
    "        stack = [(code, 0)]\n",
    "        s = 0\n",
    "        n1, n2 = len(mat), len(mat[0])\n",
    "        target = '0' * (n1 * n2)\n",
    "        while s < len(stack):\n",
    "            code, depth = stack[s]\n",
    "            if code not in searched:\n",
    "                searched[code] = depth\n",
    "            else:\n",
    "                s += 1\n",
    "                continue\n",
    "            if code == target:\n",
    "                s += 1\n",
    "                continue\n",
    "            for i in range(n1):\n",
    "                for j in range(n2):\n",
    "                    code2 = self.change(code, i, j, n1, n2)\n",
    "                    if code2 not in searched:\n",
    "                        stack.append((code2, depth + 1))\n",
    "            s += 1\n",
    "        if target in searched:\n",
    "            return searched[target]\n",
    "        else:\n",
    "            return -1 \n",
    "    \n",
    "    def change(self, code, i, j, n1, n2):\n",
    "        ks = [i * n2 + j] \n",
    "        \n",
    "        if i > 0:\n",
    "            ks.append((i-1) * n2 + j)\n",
    "        if i < n1 - 1:\n",
    "            ks.append((i+1) * n2 + j)\n",
    "        if j > 0:\n",
    "            ks.append(i * n2 + j - 1)\n",
    "        if j < n2 - 1:\n",
    "            ks.append(i * n2 + j + 1)\n",
    "        code2 = []\n",
    "        for i in range(len(code)):\n",
    "            code2.append(code[i])\n",
    "        for k in ks:\n",
    "            code2[k] = self.flip(code2[k])\n",
    "        return ''.join(code2)\n",
    "\n",
    "    def flip(self, c):\n",
    "        if c == '1':\n",
    "            return '0'\n",
    "        else:\n",
    "            return '1'\n",
    "\n",
    "    def serialize(self, matrix):\n",
    "        code = ''\n",
    "        for line in matrix:\n",
    "            code += ''.join([str(x) for x in line])\n",
    "        #code = int(code, 2)\n",
    "        return code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlips(self, mat: List[List[int]]) -> int:\n",
    "        self.m, self.n = len(mat), len(mat[0])\n",
    "\n",
    "        dq = deque([self.enconde(mat)])\n",
    "        v = set([self.enconde(mat)])\n",
    "        steps = 0\n",
    "        while dq:\n",
    "            size = len(dq)\n",
    "            while size:\n",
    "                o = dq.popleft()\n",
    "                if o == 0:\n",
    "                    return steps\n",
    "                for i in range(self.m):\n",
    "                    for j in range(self.n):\n",
    "                        p = self.convert(o, i, j)\n",
    "                        # if p == 60:\n",
    "                        print(i, j, o, bin(o), bin(p))\n",
    "                        if p in v:\n",
    "                            continue\n",
    "                        dq.append(p)\n",
    "                        v.add(p)\n",
    "                size -= 1\n",
    "            steps += 1\n",
    "        return -1\n",
    "\n",
    "    def enconde(self, mat: List[List[int]]) -> int:\n",
    "        num = 0\n",
    "        for i, row in enumerate(mat):\n",
    "            for j, x in enumerate(row):\n",
    "                if x:\n",
    "                    num |= (1 << (i * self.n + j))\n",
    "        return num\n",
    "\n",
    "    def decode(self, num: int) -> List[List[int]]:\n",
    "        mat = [[0] * self.n for _ in range(self.m)]\n",
    "        for x in range(num.bit_length()):\n",
    "            if num & (1 << x):\n",
    "                i, j = divmod(x, self.n)\n",
    "                mat[i][j] = 1\n",
    "        return mat\n",
    "\n",
    "    def convert(self, num: int, x: int, y: int) -> List[List[int]]:\n",
    "        d = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        for dx, dy in d:\n",
    "            if 0 <= x + dx < self.m and 0 <= y + dy < self.n:\n",
    "                num ^= (1 << ((x + dx) * self.n + y + dy))\n",
    "        num ^= (1 << (x * self.n + y))\n",
    "\n",
    "        # # 同一行\n",
    "        # for y in range(i * self.n, (i + 1) * self.n):\n",
    "        #     num ^= (1 << y)\n",
    "        # # 同一列\n",
    "        # for x in range(self.m):\n",
    "        #     num ^= (1 << (x * self.n + j))\n",
    "        # num ^= (1 << (i * self.n + j))\n",
    "        return num"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
